package com.dragon.datastructure.stack;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * 中缀表达式转后缀表达式
 *
 * @author dragon
 * @since 2019/12/19
 */
public class MiddleExpression2SuffixExpression {

    /**
     * 左括号
     */
    private static final String LEFT_BRACKET = "(";

    /**
     * 右括号
     */
    private static final String RIGHT_BRACKET = ")";

    public static void main(String[] args) {
        String s = new MiddleExpression2SuffixExpression().toSuffixExpression("1+((2+3)*4)-5");
        System.out.println(s);
        SuffixExpressionCalculate suffixExpressionCalculate = new SuffixExpressionCalculate();
        System.out.println(suffixExpressionCalculate.calculate(s));
    }

    /**
     * 中缀表达式转后缀表达式
     *
     * @param middleExpression 中缀表达式
     * @return 后缀表达式
     */
    public String toSuffixExpression(String middleExpression) {
        if (middleExpression == null || middleExpression.trim() == null) {
            return null;
        }
        // 1.将中缀表达式转换为与之对应的集合
        List<String> middleExpressionList = toMiddleExpressionList(middleExpression);
        System.out.println(middleExpressionList);
        // 2.通过中缀表达式的集合解析转换成后缀表达式
        List<String> suffixExpressionList = doMiddleExpression2SuffixExpression(middleExpressionList);
        System.out.println(suffixExpressionList);

        StringBuilder sb = new StringBuilder();
        suffixExpressionList.stream().
                forEach(s -> sb.append(s).append(" "));

        return sb.toString();
    }

    /**
     * 通过中缀表达式的集合 解析 转换 成后缀表达式
     *
     * @param middleExpressionList 中缀表达式的集合
     * @return 后缀表达式
     */
    private List<String> doMiddleExpression2SuffixExpression(List<String> middleExpressionList) {
        // 初始化运算符栈
        ArrayDeque<String> operatorStack = new ArrayDeque<>();
        // 初始化操作数的集合
        List<String> result = new ArrayList<>();
        for (int i = 0; i < middleExpressionList.size(); i++) {
            String item = middleExpressionList.get(i);
            /*
             * 如果遇到数字
             */
            if (item.matches("\\d+")) {
                result.add(item);
                continue;
            }

            /*
             * 如果遇到括号
             */
            // 遇到左括号
            if (LEFT_BRACKET.equals(item)) {
                operatorStack.push(item);
                continue;
            }
            // 如果是右括号
            if (RIGHT_BRACKET.equals(item)) {
                while (!LEFT_BRACKET.equals(operatorStack.peek())) {
                    result.add(operatorStack.pop());
                }
                // 消除左括号
                operatorStack.pop();
                continue;
            }

            /*
             * 如果是操作符
             */
            // 如果栈为空或者栈顶元素为左括号
            if (operatorStack.isEmpty() || LEFT_BRACKET.equals(operatorStack.peek())) {
                operatorStack.push(item);
                continue;
            }
            // 如果遍历操作符的优先级是大于栈顶元素的优先级
            if (Operator.getPriority(item) > Operator.getPriority(operatorStack.peek())) {
                operatorStack.push(item);
                continue;
            }
            // 如果遍历操作符的优先级是小于栈顶元素的优先级,重复上述动作
            result.add(operatorStack.pop());
            i--;

        }
        // 依次弹出operatorStack中的元素添加到结果集中
        while (!operatorStack.isEmpty()) {
            result.add(operatorStack.pop());
        }

        return result;
    }

    /**
     * 将中缀表达式转换为与之对应的集合
     *
     * @param middleExpression 中缀表达式语句
     * @return 中缀表达式集合
     */
    private List<String> toMiddleExpressionList(String middleExpression) {
        ArrayList<String> list = new ArrayList<>();
        StringBuilder tmpDigit = new StringBuilder();
        for (int i = 0; i < middleExpression.length(); ) {
            if (!Character.isDigit(middleExpression.charAt(i))) {
                list.add(middleExpression.charAt(i) + "");
                i++;
                continue;
            }
            do {
                tmpDigit.append(middleExpression.charAt(i++));
            } while (i < middleExpression.length() && Character.isDigit(middleExpression.charAt(i)));
            list.add(tmpDigit.toString());
            tmpDigit.delete(0, tmpDigit.length());
        }

        return list;
    }
}

